package P1.kuaisupaixu;

import java.io.IOException;
import java.util.Scanner;

/**
 * @date:2022/8/17
 * @author:LdLtd
 * @name:快速排序
 */

/*
*
第一步，确定分界点
    先从数组中任意选择一个元素x作为分界点，这个元素可以是左边界q[l]，
    也可以是数组中间的元素q[(l+r)/2]，还可以是右边界q[r]
第二步，调整区间
    把整个区间根据x的值分为两半，让小于等于x的元素在区间的左半边，
    大于等于x的元素在区间的右半边（注意，两边的元素数不一定相等，而且x也不一定在两边的分界处）
第三步，递归
    先递归地对刚才划分出来的左半边进行排序，
    之后对右半边递归地排序

再对x位置小结：

        如果区间取[l,i-1]和[i,r]这种，那么x不应该取左边界(l、(l+r)/2)。
        应取 x = q[r]; x = q[(l+r+1)/2];

        如果区间取[l,j]和[j+1,r]这种，那么x不应该取右边界(如r、(l+r+1)/2)。
        应取 x = q[l]; x = q[(l+r)/2];
*
* */
public class QuickSort {

        public static void main(String [] args) throws IOException {
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                int[] q = new int[n];
                for(int i=0; i<n; i++){q[i] = sc.nextInt();}


                quick_sort(q,0,n-1);
                for(int i=0;i<n;i++){
                        System.out.println(q[i]+" ");
                }

        }


        public static void quick_sort(int[] q, int l, int r){
                        if(l>=r) return;
                        int x=q[l],i=l-1,j=r+1;
                        while(i<j){
                                do i++;while(q[i]<x);
                                do j--;while(q[j]>x);
                                if(i<j) swap(q,i,j);
                                /*
                                                *
                                int t = q[i];
                                q[i] = q[j];
                                q[j] = t;
                                                                   */
                        }

                        /*
                        如果最终选择i作为分治的边界，那么x不能选取q[l]，否则会因边界问题陷入死循环，正确的写法如下；
                        quick_sort(q,l,i-1);
                        quick_sort(q,i,r);
                         如果最终选择j作为分治的边界，那么x不能选取q[r]，否则会因边界问题陷入死循环，正确的写法如下；
                        quick_sort(q,l,j-1);
                        quick_sort(q,j,r);
                         */
                        quick_sort(q,l,j);
                        quick_sort(q,j+1,r);
        }

        public static void swap(int[] data, int a, int b) {
                int t = data[a];
                data[a] = data[b];
                data[b] = t;
        }



}
